package com.tys.algorithm.advanced.test.class28;

/**
 * 最长回文子串的长度
 */
public class Code01_Manacher {

    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 处理成manacher串
        // "12132" -> "#1#2#1#3#2#"
        char[] str = manacherString(s);
        // 回文半径的大小：和处理串一样长
        // 回文半径数组最大值 / 2 = 结果
        int[] pArr = new int[str.length];
        int C = -1;
        // 讲述中：R代表最右的扩成功的位置
        // 代码中：R表示失败位置，扩不到的位置，最右的扩成功位置的再下一个位置
        int R = -1;
        int max = Integer.MIN_VALUE;
        //每个中心位置扩
        for (int i = 0; i < str.length; i++) { // 0 1 2
            // 求i不用验的区域：pArr[i]
            // R第一个违规的位置，i>= R，
            // i位置扩出来的答案，i位置扩的区域，至少是多大。
            // i在R外: R <= i ，i的至少回文半径是1
            // i在R内：R > i
            // 		i的对称点i1分3种情况
            // 		1 pArr[i1]在L...R内，pArr[i] = pArr[i1]，pArr[i]小
            // 		2 pArr[i1]在外， pArr[i1] = i->R距离，i->r小
            // 		3 pArr[i1]左边压线，pArr[i1] = i->R距离，
            //			R后面也还需要继续验证, 一样小
            // i的对称点i1 = 2 * C - i
            // pArr[2 * C - i] 是 i1的半径长度
            // i->R的距离 = R-i，
            // pArr[2 * C - i]和R-i中小的就是至少不用验证的距离：两个不相等
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            //全都验：右边不越界 && 左边不越界
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                //验证：右边和左边是否相等
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    //构成回文半径++
                    pArr[i]++;
                else {
                    //不是回文退出
                    break;
                }
            }
            //求出i的回文半径，看是否会更新R
            if (i + pArr[i] > R) {
                //更新R
                R = i + pArr[i];
                //更新C
                C = i;
            }
            //最大回文半径
            max = Math.max(max, pArr[i]);
        }
        //123->#1#2#1#
        //max=4,原始的回文长度=max-1=3
        return max - 1;
    }

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    // for test
    public static int right(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = manacherString(s);
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int L = i - 1;
            int R = i + 1;
            while (L >= 0 && R < str.length && str[L] == str[R]) {
                L--;
                R++;
            }
            max = Math.max(max, R - L - 1);
        }
        return max / 2;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            if (manacher(str) != right(str)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

}
